package com.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 组合总和
 *
 * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。
 * 你可以按 任意顺序 返回这些组合。
 *
 *
 * @author winson
 * @create 2022-04-07 10:17
 */
public class CombinationSumSolution {

    /**
     * 搜索回溯
     * 递归搜索树，确定递归入参，终止条件，返回值
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> combine = new ArrayList<>();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

    private void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int i) {
        if (i == candidates.length) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<>(combine));
            return;
        }
        // 跳过当前元素
        dfs(candidates, target, ans, combine, i + 1);
        // 选择当前数
        if (target - candidates[i] >= 0) {
            // 目标数大于等于0，继续搜索下一个数
            combine.add(candidates[i]);
            dfs(candidates, target - candidates[i], ans, combine, i);
            combine.remove(combine.size() - 1);
        }
    }
}
